//
// Created by lyc on 2025/3/24.
//

#include "knapsack01.h"

/******************************************************************************************************************
 * DP(基于递归)
 * @定义数据结构
 * maxValue[surplusItems][surplusCapacity]
 * 表示剩余物品surplusItems和剩余容量surplusCapacity时， 背包的最大价值
 * 当前物品的重量和价值分别为 weight, value
 * @最优子结构
 * maxValue[s][c] =
 *     maxValue[s-1][c], c < weight
 *     max{ maxValue[s-1][c-weight] + value, maxValue[s-1][c]}, c >= weight
 *
 * @param surplusCapacity 剩余容量
 * @param it 当前物品
 * @return 当前物品价值
 ******************************************************************************************************************/
double knapsack01_DP_recursion(double surplusCapacity, vector<Item>::iterator it){

    /* 出口: 到达最后位置（哨兵） */
    if(it->id == -1){
        return 0;
    }

    if(surplusCapacity < it->weight){
        return knapsack01_DP_recursion(surplusCapacity, next(it));
    }
    else{
//        Item *item_temp = item;
        return max(
                knapsack01_DP_recursion(surplusCapacity, next(it)),
                it->value + knapsack01_DP_recursion(surplusCapacity - it->weight, next(it))
                );
    }

}

/******************************************************************************************************************
 * 贪心
 * 根据性价比排序，然后贪心
 ******************************************************************************************************************/


/**
 * @function 根据性价比进行快速排序, 降序排列
 * @param items  待排物品数组
 * @param startLocation 子数组起始位置
 * @param endLocation   子数组结束位置
 */
void quickSortByRatio(vector<Item>& items, int startLocation, int endLocation){

    if(startLocation < endLocation) {
        int pivotLocation = endLocation - 1;

        int count_lessThanPivot = -1;
        for (int i = startLocation - 1; i < endLocation; i++) {
            /*
             * 先找出大于枢轴的元素, 全部排列在前面, 如果有n个, 就将枢轴元素和第n+1个元素互换位置
             * */
            if (items[i].value / items[i].weight > items[pivotLocation].value / items[pivotLocation].weight) {
                count_lessThanPivot++;
                swap(items[startLocation - 1 + count_lessThanPivot], items[i]);
            }
        }
        /* 上方的for循环结束后, 所有大于它的元素(假设有n个)全都排列在了data数组前n位 */
        swap(items[pivotLocation], items[startLocation - 1 + count_lessThanPivot + 1]);
        /* 此时枢轴左都大于它, 右都小于它 */
        /* 对左右子数组进行递归 */


        quickSortByRatio(items, startLocation, startLocation + count_lessThanPivot);


        quickSortByRatio(items, startLocation + count_lessThanPivot + 2, endLocation);
    }
}


/**
 * @function 贪心求解01背包问题
 * @note 对于01背包问题， 该算法并不能保证一定找到最优解
 * @param capacity 背包容量
 * @param it 当前物品
 * @param items 物品序列
 * @return 当前价值
 */
double knapsack01_greedy(double capacity, vector<Item>::iterator it, vector<Item>& items){
    quickSortByRatio(items, 1, items.size());

    double totalValue = 0;

    while(capacity > 0 && it -> id != -1){
        /* 只要背包容量还够， 且没到哨兵 */
        if(capacity >= it -> weight){
            /* 能容纳下该物品 */
            capacity = capacity - (it -> weight);
            totalValue = totalValue + it -> value;
            it = next(it);

        }
        else{
            /* 不能容纳下该物品， 则切换到下一物品 */
            it = next(it);
        }
    }

    return totalValue;
}



/******************************************************************************************************************
 * DP(基于循环)
 * @最优子结构
 *  maxValue[s][c] =
 *      maxValue[s-1][c], c < weight
 *      max{ maxValue[s-1][c-weight] + value, maxValue[s-1][c]}, c >= weight
 *
 * @param capacity 背包容量
 * @param items 物品序列
 * @return 最大价值
 ******************************************************************************************************************/
double knapsack01_DP_loop(int capacity, vector<Item> items){
    /* 假设capacity是整数, weight也是整数 */
    double dp[items.size() + 1][capacity + 1] = {}; //初始化全0

    for(int i = 1; i <= items.size(); i++){
        for(int j = 1; j <= capacity; j++){
            if(items[i-1].weight > j){
                /* 不能容纳下该物品， 则切换到下一物品 */
                dp[i][j] = dp[i-1][j];
            }
            else{
                dp[i][j] = max(
                        items[i-1].value + dp[i-1][j - int(items[i-1].weight)],
                        dp[i-1][j]
                        );
            }
        }
    }

    return dp[items.size()][capacity];
}


/******************************************************************************************************************
 * 基于回溯的递归
 * 可以理解为最原始的递归算法
 ******************************************************************************************************************/
double maxValue = 0;

void knapsack01_backtrack(double surplusCapacity, vector<Item>::iterator it, double currValue) {
    if(it->id == -1){
        maxValue = max(maxValue, currValue);
        return;
    }
    knapsack01_backtrack(surplusCapacity, next(it), currValue);

    if(surplusCapacity >= (it -> weight)) {
        knapsack01_backtrack(surplusCapacity - (it->weight), next(it), currValue + (it->value));
    }
}